PittsburghV1, France, Analysis, bibRecord, 000755

New variants of lift-and-project cut generation from the LP tableau: open source implementation and testing.

Identifieur interne : 000755 ( France/Analysis ); précédent : 000754; suivant : 000756

New variants of lift-and-project cut generation from the LP tableau: open source implementation and testing.

Auteurs : Egon Balas [États-Unis] ; Pierre Bonami [France]

Source :

RBID : Hal:hal-00421759

Abstract

We discuss an open source implementation and preliminary computational testing of three variants of the Balas-Perregaard procedure for generating lift-and-project cuts from the original simplex tableau, two of which are new. Variant 1 is the original procedure with minor modifications. Variant 2 uses a new procedure for choosing the pivot element: After identifying the set of row candidates for an improving pivot, the pivot element (and column) is chosen by optimizing over the entries of all candidate rows. Finally, Variant 3 replaces the source row with its disjunctive modularization, and after each pivot it again modularizes the resulting source row. We report on computational results with the above three variants and their combinations on 65 MIPLIB.3 instances.

Url:

https://hal.archives-ouvertes.fr/hal-00421759

DOI: 10.1007/978-3-540-72792-7

Affiliations:

France, États-Unis

Links toward previous steps (curation, corpus...)

to stream Hal, to step Corpus: 000411
to stream Hal, to step Curation: 000411
to stream Hal, to step Checkpoint: 000592
to stream Main, to step Merge: 00B139
to stream Main, to step Curation: 00A986
to stream Main, to step Exploration: 00A986
to stream France, to step Extraction: 000755

Links to Exploration step

Hal:hal-00421759

Le document en format XML

<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">New variants of lift-and-project cut generation from the LP tableau: open source implementation and testing.</title>
<author><name sortKey="Balas, Egon" sort="Balas, Egon" uniqKey="Balas E" first="Egon" last="Balas">Egon Balas</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-87848" status="VALID">          <orgName>Tepper School of Business</orgName>
          <desc>            <address>              <addrLine>5000 Forbes Ave., Pittsburgh, PA 15213, USA</addrLine>
              <country key="US"></country>
            </address>
            <ref type="url">http://www.tepper.cmu.edu/</ref>
          </desc>
          <listRelation>            <relation active="#struct-67135" type="direct"></relation>
          </listRelation>
        <tutelles><tutelle active="#struct-67135" type="direct"><org type="institution" xml:id="struct-67135" status="VALID">          <orgName>Carnegie Mellon University [Pittsburgh]</orgName>
          <orgName type="acronym">CMU</orgName>
          <desc>            <address>              <addrLine>5000 Forbes Ave,  Pittsburgh, PA 15213</addrLine>
              <country key="US"></country>
            </address>
            <ref type="url">http://www.cmu.edu/</ref>
          </desc>
        </org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>États-Unis</country>
</affiliation>
</author>
<author><name sortKey="Bonami, Pierre" sort="Bonami, Pierre" uniqKey="Bonami P" first="Pierre" last="Bonami">Pierre Bonami</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-862" status="OLD">          <idno type="RNSR">200212226K</idno>
          <orgName>Laboratoire d'informatique Fondamentale de Marseille - UMR 6166</orgName>
          <orgName type="acronym">LIF</orgName>
          <date type="start">2002</date>
          <date type="end">2011</date>
          <desc>            <address>              <addrLine>CMI 39, Rue Joliot Curie 13453 MARSEILLE CEDEX 13</addrLine>
              <country key="FR"></country>
            </address>
            <ref type="url">http://www.lif.univ-mrs.fr/</ref>
          </desc>
          <listRelation>            <relation active="#struct-5033" type="direct"></relation>
            <relation active="#struct-92823" type="direct"></relation>
            <relation name="UMR6166" active="#struct-441569" type="direct"></relation>
          </listRelation>
        <tutelles><tutelle active="#struct-5033" type="direct"><org type="institution" xml:id="struct-5033" status="OLD">          <idno type="IdRef">026402882</idno>
          <orgName>Université de la Méditerranée - Aix-Marseille 2</orgName>
          <date type="start">1969</date>
          <date type="end">2011</date>
          <desc>            <address>              <addrLine>58, boulevard Charles Livon - 13284 Marseille cedex 07</addrLine>
              <country key="FR"></country>
            </address>
            <ref type="url">http://www.univmed.fr/</ref>
          </desc>
        </org>
</tutelle>
<tutelle active="#struct-92823" type="direct"><org type="institution" xml:id="struct-92823" status="OLD">          <idno type="IdRef">026403781</idno>
          <orgName>Université de Provence - Aix-Marseille 1</orgName>
          <date type="end">2011-12-31</date>
          <desc>            <address>              <addrLine>3, place Victor Hugo - 13331 Marseille Cedex 03</addrLine>
              <country key="FR"></country>
            </address>
            <ref type="url">http://www.univ-provence.fr/</ref>
          </desc>
        </org>
</tutelle>
<tutelle name="UMR6166" active="#struct-441569" type="direct"><org type="institution" xml:id="struct-441569" status="VALID">          <idno type="IdRef">02636817X</idno>
          <idno type="ISNI">0000000122597504</idno>
          <orgName>Centre National de la Recherche Scientifique</orgName>
          <orgName type="acronym">CNRS</orgName>
          <date type="start">1939-10-19</date>
          <desc>            <address>              <country key="FR"></country>
            </address>
            <ref type="url">http://www.cnrs.fr/</ref>
          </desc>
        </org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">HAL</idno>
<idno type="RBID">Hal:hal-00421759</idno>
<idno type="halId">hal-00421759</idno>
<idno type="halUri">https://hal.archives-ouvertes.fr/hal-00421759</idno>
<idno type="url">https://hal.archives-ouvertes.fr/hal-00421759</idno>
<idno type="doi">10.1007/978-3-540-72792-7</idno>
<date when="2007-06-25">2007-06-25</date>
<idno type="wicri:Area/Hal/Corpus">000411</idno>
<idno type="wicri:Area/Hal/Curation">000411</idno>
<idno type="wicri:Area/Hal/Checkpoint">000592</idno>
<idno type="wicri:explorRef" wicri:stream="Hal" wicri:step="Checkpoint">000592</idno>
<idno type="wicri:Area/Main/Merge">00B139</idno>
<idno type="wicri:Area/Main/Curation">00A986</idno>
<idno type="wicri:Area/Main/Exploration">00A986</idno>
<idno type="wicri:Area/France/Extraction">000755</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en">New variants of lift-and-project cut generation from the LP tableau: open source implementation and testing.</title>
<author><name sortKey="Balas, Egon" sort="Balas, Egon" uniqKey="Balas E" first="Egon" last="Balas">Egon Balas</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-87848" status="VALID">          <orgName>Tepper School of Business</orgName>
          <desc>            <address>              <addrLine>5000 Forbes Ave., Pittsburgh, PA 15213, USA</addrLine>
              <country key="US"></country>
            </address>
            <ref type="url">http://www.tepper.cmu.edu/</ref>
          </desc>
          <listRelation>            <relation active="#struct-67135" type="direct"></relation>
          </listRelation>
        <tutelles><tutelle active="#struct-67135" type="direct"><org type="institution" xml:id="struct-67135" status="VALID">          <orgName>Carnegie Mellon University [Pittsburgh]</orgName>
          <orgName type="acronym">CMU</orgName>
          <desc>            <address>              <addrLine>5000 Forbes Ave,  Pittsburgh, PA 15213</addrLine>
              <country key="US"></country>
            </address>
            <ref type="url">http://www.cmu.edu/</ref>
          </desc>
        </org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>États-Unis</country>
</affiliation>
</author>
<author><name sortKey="Bonami, Pierre" sort="Bonami, Pierre" uniqKey="Bonami P" first="Pierre" last="Bonami">Pierre Bonami</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-862" status="OLD">          <idno type="RNSR">200212226K</idno>
          <orgName>Laboratoire d'informatique Fondamentale de Marseille - UMR 6166</orgName>
          <orgName type="acronym">LIF</orgName>
          <date type="start">2002</date>
          <date type="end">2011</date>
          <desc>            <address>              <addrLine>CMI 39, Rue Joliot Curie 13453 MARSEILLE CEDEX 13</addrLine>
              <country key="FR"></country>
            </address>
            <ref type="url">http://www.lif.univ-mrs.fr/</ref>
          </desc>
          <listRelation>            <relation active="#struct-5033" type="direct"></relation>
            <relation active="#struct-92823" type="direct"></relation>
            <relation name="UMR6166" active="#struct-441569" type="direct"></relation>
          </listRelation>
        <tutelles><tutelle active="#struct-5033" type="direct"><org type="institution" xml:id="struct-5033" status="OLD">          <idno type="IdRef">026402882</idno>
          <orgName>Université de la Méditerranée - Aix-Marseille 2</orgName>
          <date type="start">1969</date>
          <date type="end">2011</date>
          <desc>            <address>              <addrLine>58, boulevard Charles Livon - 13284 Marseille cedex 07</addrLine>
              <country key="FR"></country>
            </address>
            <ref type="url">http://www.univmed.fr/</ref>
          </desc>
        </org>
</tutelle>
<tutelle active="#struct-92823" type="direct"><org type="institution" xml:id="struct-92823" status="OLD">          <idno type="IdRef">026403781</idno>
          <orgName>Université de Provence - Aix-Marseille 1</orgName>
          <date type="end">2011-12-31</date>
          <desc>            <address>              <addrLine>3, place Victor Hugo - 13331 Marseille Cedex 03</addrLine>
              <country key="FR"></country>
            </address>
            <ref type="url">http://www.univ-provence.fr/</ref>
          </desc>
        </org>
</tutelle>
<tutelle name="UMR6166" active="#struct-441569" type="direct"><org type="institution" xml:id="struct-441569" status="VALID">          <idno type="IdRef">02636817X</idno>
          <idno type="ISNI">0000000122597504</idno>
          <orgName>Centre National de la Recherche Scientifique</orgName>
          <orgName type="acronym">CNRS</orgName>
          <date type="start">1939-10-19</date>
          <desc>            <address>              <country key="FR"></country>
            </address>
            <ref type="url">http://www.cnrs.fr/</ref>
          </desc>
        </org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
</affiliation>
</author>
</analytic>
<idno type="DOI">10.1007/978-3-540-72792-7</idno>
</biblStruct>
</sourceDesc>
</fileDesc>
<profileDesc><textClass></textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">We discuss an open source implementation and preliminary computational testing of three variants of the Balas-Perregaard procedure for generating lift-and-project cuts from the original simplex tableau, two of which are new. Variant 1 is the original procedure with minor modifications. Variant 2 uses a new procedure for choosing the pivot element: After identifying the set of row candidates for an improving pivot, the pivot element (and column) is chosen by optimizing over the entries of all candidate rows. Finally, Variant 3 replaces the source row with its disjunctive modularization, and after each pivot it again modularizes the resulting source row. We report on computational results with the above three variants and their combinations on 65 MIPLIB.3 instances.</div>
</front>
</TEI>
<affiliations><list><country><li>France</li>
<li>États-Unis</li>
</country>
</list>
<tree><country name="États-Unis"><noRegion><name sortKey="Balas, Egon" sort="Balas, Egon" uniqKey="Balas E" first="Egon" last="Balas">Egon Balas</name>
</noRegion>
</country>
<country name="France"><noRegion><name sortKey="Bonami, Pierre" sort="Bonami, Pierre" uniqKey="Bonami P" first="Pierre" last="Bonami">Pierre Bonami</name>
</noRegion>
</country>
</tree>
</affiliations>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/Amérique/explor/PittsburghV1/Data/France/Analysis

HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000755 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/France/Analysis/biblio.hfd -nk 000755 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Wicri/Amérique
   |area=    PittsburghV1
   |flux=    France
   |étape=   Analysis
   |type=    RBID
   |clé=     Hal:hal-00421759
   |texte=   New variants of lift-and-project cut generation from the LP tableau: open source implementation and testing.
}}

This area was generated with Dilib version V0.6.38.
Data generation: Fri Jun 18 17:37:45 2021. Site generation: Fri Jun 18 18:15:47 2021

	Serveur d'exploration sur Pittsburgh
	Attention, ce site est en cours de développement ! Attention, site généré par des moyens informatiques à partir de corpus bruts. Les informations ne sont donc pas validées.

Serveur d'exploration sur Pittsburgh

New variants of lift-and-project cut generation from the LP tableau: open source implementation and testing.

New variants of lift-and-project cut generation from the LP tableau: open source implementation and testing.

Source :

Abstract

Links toward previous steps (curation, corpus...)

Links to Exploration step

Le document en format XML

Pour manipuler ce document sous Unix (Dilib)

Pour mettre un lien sur cette page dans le réseau Wicri